home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.11 Nov 93 / Programmers' Challenge / BlockMoveBits.c
Encoding:
C/C++ Source or Header  |  1994-11-06  |  3.5 KB  |  165 lines  |  [TEXT/KAHL]
  1. /*
  2. ** BlockMoveBits by Bob Boonstra
  3. **
  4. ** Solution strategy:
  5. **   Use 68030 bit field manipulation instructions
  6. **     rather than shifting and masking.
  7. **   Accomplish move in three steps, where the first step
  8. **     aligns destination to longword, second step uses
  9. **     BFEXTU/MOVE.L combination instead of BFEXTU/BFINS to
  10. **     move bulk of the bits, and third step cleans up.
  11. **   Special case when srcBitOffset==destBitOffset,
  12. **     allowing main loop to use MOVE.L (x)+,(y)+
  13. **
  14. ** Relative execution times for various strategies:
  15. ** 100: Straigntforward BFEXTU/BFINS in 32-bit chunks,
  16. **  70: byte-align src and MOVE.L/BFINS in main loop,
  17. **  58: byte-align dst and BFEXTU/MOVE.L in main loop,
  18. **  50: long-aligned dst and BFEXTU/MOVE.L in main loop,
  19. **  29: as above, if srcOffset==dstOffset use one MOVE.L
  20. */
  21.  
  22. /* some register definitions for readability */
  23. #define bitCt     d2
  24. #define srcOffset d6
  25. #define dstOffset d7
  26. #define srcPtr    a0
  27. #define dstPtr    a1
  28.  
  29. void BlockMoveBits(char *srcBytePtr, char *destBytePtr, 
  30.   unsigned char srcBitOffset, unsigned char destBitOffset, 
  31.   unsigned short bitCount)
  32. {
  33.   asm 68030 {
  34.   
  35. ; save registers
  36.  
  37.     MOVEM.L   d6-d7,-(a7)
  38.     
  39. ; exit if no bits to move
  40.  
  41.     MOVEQ     #0,bitCt
  42.     MOVE.W    bitCount,bitCt
  43.     
  44. ; get params into registers
  45.  
  46.     MOVE.L    srcBytePtr,srcPtr
  47.     MOVE.L    destBytePtr,dstPtr
  48.     MOVE.B    srcBitOffset,d1
  49.     MOVEQ     #0,d0
  50.     MOVE.B    destBitOffset,d0
  51.     
  52. ; calculate srcOffset and dstOffset in
  53. ;   bit field manipulation coordinates 
  54. ;   (bit 0 is MSB)
  55.  
  56.     MOVEQ     #7,srcOffset    
  57.     SUB.B     d1,srcOffset
  58.     MOVEQ     #7,dstOffset
  59.     SUB.B     d0,dstOffset
  60.     
  61. ; exit if <= 32 bits to move
  62.  
  63.     CMPI.L     #32,bitCt
  64.     BLE       @lastbits
  65.     
  66. ; convert dstOffset to initial bit count
  67.  
  68.     ADDQ.W    #1,d0
  69.  
  70. ; STEP 1:  Move enough bits to longAlign destination
  71. ;          using bit field manipulation
  72.  
  73. ; adjust bit count to longAlign destination
  74.  
  75.     MOVE.W    dstPtr,d1
  76.     ANDI.B    #3,d1
  77.     EORI.B    #3,d1
  78.     LSL.B     #3,d1
  79.     ADD.B     d1,d0
  80.     
  81. ; move initial bits
  82.  
  83.     BFEXTU    (srcPtr){srcOffset:d0},d1
  84.     BFINS     d1,(dstPtr){dstOffset:d0}
  85.     
  86. ; decrement bits left to move
  87.  
  88.     SUB.L     d0,bitCt
  89.     
  90. ; adjust source offset; this may make
  91. ; srcOffset >= 8, but BFEXTU does not care
  92.  
  93.     ADD.W     d0,srcOffset
  94.     
  95. ; adjust dstPtr to account for alignment
  96.  
  97.     LSR.B     #3,d0
  98.     ADDQ.B    #1,d0
  99.     ADDA.W    d0,dstPtr
  100.     MOVEQ     #0,dstOffset
  101.  
  102. ; STEP 2:  Main loop, MOVE.L all 32-bit chunks
  103.  
  104. ; set up d0 with number of longwords to move
  105.  
  106.     MOVE.W    bitCt,d0
  107.     LSR.W     #5,d0
  108.     BLE       @lastbits
  109.     
  110. ; set up bitCt for final BFEXTU/BFINS
  111.  
  112.     ANDI.W    #31,bitCt
  113.     
  114. ; decrement d0 for subsequent DBRA
  115.  
  116.     SUBQ.W    #1,d0
  117.     
  118. ; move bits one longword at a time
  119.  
  120.     MOVE.B    srcOffset,d1
  121.     ANDI.B    #7,d1
  122.     BNE.S     @longloop
  123.     
  124. ; special case, src is byte-aligned
  125.  
  126.     LSR.B     #3,srcOffset
  127.     ADDA.L    srcOffset,srcPtr
  128.     MOVEQ     #0,srcOffset
  129.     
  130. alignloop:
  131.  
  132.     MOVE.L    (srcPtr)+,(dstPtr)+
  133.     DBRA      d0,@alignloop
  134.     BRA.S     @lastbits
  135.     
  136. ; normal case, src not byte-aligned
  137.  
  138. longloop:
  139.  
  140.     BFEXTU    (srcPtr){srcOffset:0},d1
  141.     MOVE.L    d1,(dstPtr)+
  142.     ADDQ.L    #4,srcPtr
  143.     DBRA      d0,@longloop
  144.  
  145. ; STEP 3:  Move remaining bits with bit field
  146. ;          manipulation
  147.  
  148. lastbits:
  149.  
  150.     TST.B     bitCt
  151.     BEQ.S     @done
  152.     
  153. ; move leftover bits
  154.  
  155.     BFEXTU    (srcPtr){srcOffset:bitCt},d1
  156.     BFINS     d1,(dstPtr){dstOffset:bitCt}
  157.     
  158. done:
  159.  
  160. ; restore registers
  161.  
  162.     MOVEM.L   (a7)+,d6-d7
  163.   }
  164. }
  165.